// https://leetcode.cn/problems/top-k-frequent-words/description/

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <queue>
#include <algorithm>

// 算法思路总结：
// 1. 哈希表统计每个单词的出现频率
// 2. 维护大小为K的最小堆，堆顶是当前第K频繁的单词
// 3. 自定义比较器：频率低的在堆顶，频率相同时字典序大的在堆顶
// 4. 最后将堆中元素逆序得到频率从高到低的结果
// 5. 时间复杂度：O(nlogk)，空间复杂度：O(n)

class Solution 
{
public:
    typedef pair<string, int> PSI;
    struct Compare
    {
        // 小根堆
        bool operator()(const PSI& p1, const PSI& p2)
        {
            if (p1.second == p2.second)
                return p1.first < p2.first;
            return p1.second > p2.second;
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        unordered_map<string, int> up;
        for (const string& str : words)
            up[str]++;

        priority_queue<PSI, vector<PSI>, Compare> Heap;

        for (const auto& [word, cnt] : up)
        {
            Heap.emplace(word, cnt);
            if (Heap.size() > k) Heap.pop();
        }

        vector<string> ret;
        while (!Heap.empty())
        {
            ret.push_back(Heap.top().first);
            Heap.pop();
        }
        reverse(ret.begin(), ret.end());

        return ret;
    }
};

int main()
{
    int k1 = 2, k2 = 4;
    vector<string> v1 = {"i", "love", "leetcode", "i", "love", "coding"};
    vector<string> v2 = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
    Solution sol;

    auto r1 = sol.topKFrequent(v1, k1);
    auto r2 = sol.topKFrequent(v2, k2);

    for (const string& str : r1)
        cout << str << " ";
    cout << endl;

    for (const string& str : r2)
        cout << str << " ";
    cout << endl;



    return 0;
}
